//给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 
//
// 示例 1: 
//
// 输入: 1->1->2
//输出: 1->2
// 
//
// 示例 2: 
//
// 输入: 1->1->2->3->3
//输出: 1->2->3 
// Related Topics 链表 
// 👍 411 👎 0

package leetcode.editor.cn;

import common.bean.ListNode;
import common.util.MyUtil;

/**
 * Java：删除排序链表中的重复元素
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P83_RemoveDuplicatesFromSortedList {
    public static void main(String[] args) {
        Solution solution = new P83_RemoveDuplicatesFromSortedList().new Solution();
        MyUtil.printListNode(solution.deleteDuplicates(MyUtil.createNode(1, 1, 2, 3, 4, 4)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 迭代
     */
//    class Solution {
//        public ListNode deleteDuplicates(ListNode head) {
//            for (ListNode curr = head; curr != null && curr.next != null; ) {
//                if (curr.val == curr.next.val) {
//                    curr.next = curr.next.next;
//                } else {
//                    curr = curr.next;
//                }
//            }
//            return head;
//        }
//    }

    /**
     * 递归
     */
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }
            head.next = deleteDuplicates(head.next);
            if(head.val == head.next.val) {
                ListNode next = head.next;
                head = head.next;
                // 内存管理，加速回收
                next = null;
            }
            return head;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}